/**
 * 
 */
package leetCode;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author zhongfang
 *
 */
public class LongestSubstringWithoutRepeatingCharacters {
	public int lengthOfLongestSubstring(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		int left = 0, right = 0, len = 0;
		int n = s.length();
		HashMap<Character, Integer> map = new HashMap<>();
		while (right < n) {
			if (map.containsKey(s.charAt(right))) {
				left = map.get(s.charAt(right)) + 1;
			}
			len = Math.max(len, right - left + 1);
			map.put(s.charAt(right), right);
			right++;
		}
		return len;
	}

	public int lengthOfLongestSubstring2(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		int left = 0, right = 0;
		HashSet<Character> set = new HashSet<>();
		int len = 0;
		int n = s.length();
		while (true) {
			while (right < n && set.add(s.charAt(right))) {
				right++;
			}
			// System.out.println(right + " " + left);
			len = Math.max(len, right - left);// right处于重复的位置
			if (right == n) {
				break;
			}
			while (left < right && s.charAt(left) != s.charAt(right)) { // 直到当前left的字符==right的字符
				set.remove(s.charAt(left));
				left++;
			}
			// set.remove(left);
			if (left != right) {
				left++;
			}
			right++;
		}
		return len;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String s = "abba";
		System.out.println(new LongestSubstringWithoutRepeatingCharacters().lengthOfLongestSubstring(s));
	}

}
